import threading
import time
import random


# --- 核心组件：死锁检测器 ---
# 这是您要挑战和替换的经典基线（基于DFS的环路检测）
def find_deadlock(processes, resources):
    """
    分析当前所有进程和资源的状态，构建等待图并检测是否存在环路。

    返回:
        一个包含死锁环中进程的列表，例如 ['P1', 'P2', 'P3']。
        如果没有死锁，则返回 None。
    """

    # 1. 构建资源持有者映射 (resource -> process)
    #    和进程等待映射 (process -> resource)
    #    这是从“真实”线程状态中抽象出逻辑关系的关键一步
    holds_map = {}
    waits_map = {}

    # 为了线程安全，我们快速抓取一个快照状态
    for p in processes:
        p.lock.acquire()  # 保护进程内部状态
        if p.holding:
            for r_name in p.holding:
                holds_map[r_name] = p.name
        if p.waiting_for:
            waits_map[p.name] = p.waiting_for
        p.lock.release()

    # 2. 构建进程等待图 (process -> process)
    #    例如: P1在等P2，P2在等P3...
    wait_for_graph = {p.name: None for p in processes}
    for p_name, r_name in waits_map.items():
        if r_name in holds_map:
            wait_for_graph[p_name] = holds_map[r_name]

    # 3. 使用DFS检测环路
    path = set()
    visited = set()

    for p_name in wait_for_graph:
        if p_name not in visited:
            # 从每个未访问过的节点开始深度优先搜索
            deadlock_cycle = dfs_check(p_name, wait_for_graph, path, visited)
            if deadlock_cycle:
                # 调整顺序，让起点和终点一致
                start_node = deadlock_cycle[0]
                first_occurrence = deadlock_cycle.index(start_node, 1)
                return deadlock_cycle[first_occurrence - 1:]
    return None


def dfs_check(node, graph, path, visited):
    """DFS辅助函数"""
    if node is None:
        return None

    path.add(node)
    visited.add(node)

    next_node = graph.get(node)

    if next_node in path:
        # 发现环路！
        return [next_node, node]

    if next_node and next_node not in visited:
        cycle = dfs_check(next_node, graph, path, visited)
        if cycle:
            cycle.append(node)
            return cycle

    path.remove(node)
    return None


# --- 模拟环境组件 ---

class Process(threading.Thread):
    def __init__(self, name, resource_requests):
        """
        name: 进程名 (e.g., 'P1')
        resource_requests: 一个资源名列表，代表它需要按顺序获取的资源
        """
        super().__init__(name=name)
        self.resource_requests = resource_requests

        # 内部状态变量
        self.holding = set()
        self.waiting_for = None

        # 保护内部状态的锁
        self.lock = threading.Lock()

    def run(self):
        global resources
        print(f"[{self.name}] 启动，需要资源: {self.resource_requests}")

        for r_name in self.resource_requests:
            print(f"[{self.name}] 尝试获取资源 {r_name}...")

            # 更新等待状态
            with self.lock:
                self.waiting_for = r_name

            # 阻塞式获取资源
            resource_lock = resources[r_name]
            acquired = resource_lock.acquire()

            if acquired:
                print(f"[{self.name}] 成功获取资源 {r_name}")
                with self.lock:
                    self.holding.add(r_name)
                    self.waiting_for = None

                # 模拟工作
                time.sleep(random.uniform(0.1, 0.3))

        print(f"[{self.name}] 工作完成，释放所有资源: {self.holding}")
        for r_name in self.holding:
            resources[r_name].release()

        # 清理状态
        with self.lock:
            self.holding.clear()
            self.waiting_for = None


# --- 主程序：测试场景 ---

if __name__ == "__main__":
    # 1. 定义系统中的资源
    resource_names = ['R1', 'R2', 'R3']
    resources = {name: threading.Lock() for name in resource_names}

    # 2. 定义进程及其资源请求序列，以创造死锁
    # P1: 请求 R1 -> R2
    # P2: 请求 R2 -> R1
    # P3: 请求 R3 (不会参与死锁)
    process_definitions = {
        'P1': ['R1', 'R2'],
        'P2': ['R2', 'R1'],
        'P3': ['R3'],
    }

    processes = [Process(name, reqs) for name, reqs in process_definitions.items()]

    # 3. 启动所有进程
    for p in processes:
        p.start()

    # 4. 启动监控线程/主循环来检测死锁
    print("\n--- 死锁监控启动 ---")
    time.sleep(1)  # 等待线程开始请求资源

    while any(p.is_alive() for p in processes):
        deadlock_cycle = find_deadlock(processes, resources)

        if deadlock_cycle:
            print(f"\n!!! 检测到死锁 !!!")
            print(f"死锁循环链: {' -> '.join(reversed(deadlock_cycle))}")

            # --- 这是您的模型介入的地方！---
            # deadlock_cycle 就是你模型的输入
            # model_input = deadlock_cycle
            # victim = your_model.predict(model_input)
            # print(f"AI模型建议终止进程: {victim}")
            #
            # # 在这里可以添加解锁逻辑，例如终止某个线程
            # # (注意：在Python中安全地终止线程很复杂，
            # # 在模拟中通常设置一个停止标志位)
            # break

            # 简单演示，直接退出
            print("监控退出。真实场景下应执行解锁策略。")
            # os._exit(1) # 强制退出以停止死锁的线程
            break

        else:
            print("系统状态正常，未检测到死锁...")

        time.sleep(2)

    # 等待所有线程结束
    for p in processes:
        p.join(timeout=1)

    print("\n--- 监控结束 ---")

